#include <stdio.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <sys/mman.h>
#include <fcntl.h>
#include <string.h>
#include <stdlib.h>
#include <unistd.h>
#include "common.h"

struct sortObject{
	int key;
	int id;	
};

static void bubbleSort(struct sortObject *obj, int start,int num){

	for(int i=start;i<start+num-1;i++){
		struct sortObject tmp = obj[i];
		int pos = i;
		for(int j=i+1;j<start+num;j++){
			if(obj[j].key < tmp.key){
				tmp = obj[j];
				pos = j;
			}
		}
		obj[pos] = obj[i];
		obj[i] = tmp;
		
	}
}

// start to middle-1(inclusive) is the first part
// middle to end is the second part
// start, middle, and end are all array indexes

static void mergeSort(struct sortObject *obj, int start, int middle, int end){

	int firstNum = middle - start;
	int secondNum = end - middle + 1;

	if(firstNum > 1000){
		int mid = firstNum/2;
		mergeSort(obj, start, start+mid,middle-1);
	}else{
		bubbleSort(obj, start, firstNum);
	}

	if(secondNum > 1000){
		int mid = secondNum /2;
		mergeSort(obj, middle, middle+mid, end);
	}else{
		bubbleSort(obj, middle, secondNum);
	}

	struct sortObject * result = (struct sortObject *) malloc(sizeof(struct sortObject) * (end-start+1));
	if(!result){
		printf("Malloc failed in merge sort. Not enough memory.\n");
		exit(-1);
	}

	int i,j,k;
	for(i = start, j = middle, k=0; i<=middle-1 &&j<=end;){
		if(obj[i].key < obj[j].key){
			result[k++] = obj[i++];
		}else{
			result[k++] = obj[j++];
		}
	}

	while(i<=middle-1){
		result[k++] = obj[i++];
	}

	while(j<=end)
		result[k++] = obj[j++];

	memcpy(&obj[start],result, sizeof(struct sortObject)*(end-start+1));

	free(result);

}

static void primarySort(struct sortObject * obj, int num){
	int start = 0, middle = num/2, end = num-1;

	mergeSort(obj,start,middle,end);

}




int main(int argc, char ** argv){

	if(argc != 4){
		printf("./rle fact_column dim_column outputColumn\n");
		exit(-1);
	}

	int loFd = open(argv[1],O_RDONLY);
	if(loFd == -1){
		printf("Failed to open fact file\n");
		exit(-1);
	}

	int dimFd = open(argv[2], O_RDONLY);
	if(dimFd == -1){
		printf("Failed to open dim file\n");
		exit(-1);
	}

	struct columnHeader header;
	read(dimFd, &header, sizeof(struct columnHeader));
	int dimNum = header.tupleNum;
        int dimSize = lseek(dimFd,sizeof(struct columnHeader),SEEK_END);
        char *table =(char *) mmap(0,dimSize + sizeof(struct columnHeader),PROT_READ,MAP_SHARED,dimFd,0);
	int *dimContent = (int *)malloc(dimSize);
        memcpy(dimContent,table + sizeof(struct columnHeader),dimSize);
        munmap(table,dimSize + sizeof(struct columnHeader));
	close(dimFd);

	struct sortObject * obj = (struct sortObject *) malloc(sizeof(struct sortObject ) * dimNum);

	if(!obj){
		printf("Malloc failed. Not enough memory!\n");
		exit(-1);
	}

	for(int i=0;i<dimNum;i++){
		obj[i].key = dimContent[i]; 
		obj[i].id = i+1;
	}

	primarySort(obj,dimNum);

	read(loFd, &header, sizeof(struct columnHeader));
	long tupleNum = header.tupleNum;

        long size = lseek(loFd,sizeof(struct columnHeader),SEEK_END);
        int *factContent = (int *) malloc(size);
        table =(char *) mmap(0,size + sizeof(struct columnHeader),PROT_READ,MAP_SHARED,loFd,0);
        memcpy(factContent,table + sizeof(struct columnHeader),size);
        munmap(table,size + sizeof(struct columnHeader));
        close(loFd);

	int outFd = open(argv[3],O_RDWR|O_CREAT);
	if(outFd == -1){
		printf("Failed to create output column\n");
		exit(-1);
	}

	write(outFd, &header, sizeof(struct columnHeader));

	for(long i=0;i<tupleNum;i++){
		int curr = factContent[i];
		int value = obj[curr-1].id;

		write(outFd,&value,sizeof(int));
	}

	close(outFd);
	close(loFd);
	close(dimFd);

	return 0;

}
